package Algorithm.search;

/**
 * 69. x 的平方根 https://leetcode.cn/problems/sqrtx
 * 题目简述：给你一个非负整数x，计算并返回x的算术平方根，为小数则向下取整。
 */
public class MySqrt {

    /**
     * 思路：二分查找。即从[0,(x >> 1) + (x & 1)]中二分查找平方值等于x的，
     * 定义区间[0,low)为平方值小于x的，(high,s]为平方值大于x的，最后若low越过high返回high即可
     */
    public int mySqrt(int x) {
        int low = 0, high = (x >> 1) + (x & 1);
        while (low <= high) {
            int mid = low + high >> 1;
            long num = (long) mid * mid; //注意mid * mid可能会超过int的表示范围
            if (num == x) {
                return mid;
            } else if (num < x) low = mid + 1;
            else high = mid - 1;
        }
        return high; //high即为向下取整的平方根
    }

    public static void main(String[] args) {
        System.out.println(new MySqrt().mySqrt(2147395599));
    }
}
